It took me a while to understand what binary search was actually binary searching for. Now that I understand, it's actually pretty simple:

• Set the search range between min=(largest single value) and max=(sum of all values).
  The min starts there because we're looking for the sum of the largest group in the final set of groups. And no matter what groups you create, the largest value has to be in it, so the largest group can't be smaller than that. (This assumes no negative numbers.)

• Calculate the midpoint between min and max. This midpoint is the group size we're going to try out to see how well it performs.

• Split the nums list into groups such that no group has a value larger than the chosen midpoint.
  Note that we may end up with too many or too few groups. That's fine.

• Compare the number of groups we created against the target m. If we created too many groups, we know the final answer must be between mid+1 and max. That's because we need fewer groups and the way to achieve fewer groups is to increase the allowed maximum sum in each group.

• On the other hand, if the number of groups is too small, we know the final answer is between min and mid-1 because we need to increase the number of groups which means the target sum is something smaller than the one we used. This is actually also a possible answer assuming m is valid because you can always take any group and split it up to make more groups, so the mid value you targeted is at worst, higher than the real value.

• On the third hand, if the number of groups is just right, we have a possible answer, so remember that answer. However, we should keep searching just in case there is a better answer. We're ultimately looking for smaller maximum sums, so the potentially better answer is between min and mid-1.

• Repeat the process until there is nothing else to search. Then use the minimum value we found during the above process.

Approach #2 is actually confusing. The author mix base condition with the transition. Took me some time to figure out. This is more clear

        for (int i=1;i<=n;i++)
            dp[i][1] = sub[i];
        for (int i=1;i<=n;i++){
            for (int j=2;j<=m && j<=i;j++){
                for (int k=1;k<i;k++){
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j-1], sub[i]-sub[k]));
                }
            }
        }

Such a Pathetic explanation!!!!!

I don't know why leetcode solution explanations are so poor. And let's not even mention the code readability! Leetcode needs to do a better job at filtering and editing these articles.
Here is the same question solved on geek for geeks with great explanation on how the Approach 3 works! - https://www.geeksforgeeks.org/split-the-given-array-into-k-sub-arrays-such-that-maximum-sum-of-all-sub-arrays-is-minimum/

Question #2: I also don't understand why mid, a value that is never explicitly constrained to be a sum of the subarrays, will correspond to the sum of the subarrays. Thanks!

Python solution for approach 2 throws TLE.

I wish all articles in leetcode was so nicely explained, comprehensible and precise.

Just want to improve the 2nd Approach from two aspects. First, since the minimax sum of k splits only depends on the case of k-1 splits, we may reduce the space complexity from O(m*n) to O(n). Second, the minimax sum of subarrays of nums[:j-1] must be less than or equal to that of nums[:j], so we can apply a binary search instead of the linear search when updating the dp array. The time complexity is thus reduced from O(n^2*m) to O((nlog n) * m). Below shows my python implementation.

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        
        # calculate the cumulative sum of nums[:i], so sum(nums[j:i]) = cumsum[i] - cumsum[j]
        cumsum = [0] * (n + 1)
        for i in range(n):
            cumsum[i + 1] = cumsum[i] + nums[i]
        
        # minimax of one subarray
        dp = list(cumsum)
        
        for k in range(1, m):         # at most m - 1 splits
            for i in range(n, k, -1): # to do k splits, we must have k + 1 numbers, so the minimum i equals k + 1.
                # binary search where dp[j] == sum(nums[j:i]). j ranges from k to i - 1
                left, right = k, i - 1
                while left <= right:
                    mid = (left + right) // 2
                    if dp[mid] >= cumsum[i] - cumsum[mid]:
                        right = mid - 1
                    else:
                        left = mid + 1
                dp[i] = min(max(dp[right], cumsum[i] - cumsum[right]), max(dp[left], cumsum[i] - cumsum[left]))
        
        return dp[-1]

To pass all test cases if using DP in python3:

class Solution:
    def splitArray(self, nums, m):
        dp = [[float("inf")] * (len(nums) + 1) for _ in range(m + 1)]
        dp[0][0] = 0
        # accumulative sum
        accu_sum = [0] * (len(nums) + 1)
        for j in range(len(nums)):
            accu_sum[j+1] = accu_sum[j] + nums[j]
        
        for i in range(1, m + 1):
            for j in range(1, len(nums) + 1):
                for k in range(j-1, -1, -1):
                    dp[i][j] = min(dp[i][j], max(dp[i-1][k], accu_sum[j]-accu_sum[k]))
                    ## already found the smallest largest subarray sum, stop
                    if accu_sum[j] - accu_sum[k] > dp[i-1][k]:
                        break
    
        return dp[-1][-1]

Here's a Python version of the DP approach:

class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        nlen = len(nums)
        dp = [[sys.maxint] * (m + 1) for _ in range(nlen + 1)]
        dp[0][0] = 0
        presum = [0] * (nlen + 1)
        for i, n in enumerate(nums):
            presum[i + 1] = n + presum[i]
        
        for i in range(1, nlen + 1):
            for j in range(1, m + 1):
                for k in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[k][j - 1], presum[i] - presum[k]))
        
        return dp[nlen][m]